package com.s7.search;

import java.util.Arrays;

import com.s6.sort1.ArrayUtils;
import com.s6.sort1.InsertionSort;

/**
 * 二分查找 + 变形
 */
public class Bsearch {

	public static void main(String[] args) {
		int[] array = ArrayUtils.randomInt();
		InsertionSort.sort(array);
		System.out.println("array = " + Arrays.toString(array));
		System.out.println(bsearch(array, 1));
		System.out.println(bsearchInternally(array, 2));
		System.out.println(bsearch(array, 3));
		System.out.println(bsearchInternally(array, 4));
		
		array = new int[] {1, 3, 4, 5, 6, 8, 8, 8, 11, 18};
		System.out.println(searchFirstEquals(array, 8));
		System.out.println(searchFirstGreateThanEquals(array, 10));
		System.out.println(searchLastLessThanEquals(array, 10));
		System.out.println(searchLastEquals(array, 8));
	}

	/**
	 * 二分查找的非递归实现
	 * 
	 * @param array
	 *            数组
	 * @param value
	 *            要寻找的值
	 * @return 返回的位置，若找不到则为 -1
	 */
	public static int bsearch(int[] array, int value) {
		int start = 0;
		int end = array.length - 1;
		int mid;
		int find = -1;
		while (start <= end) {
			mid = start + ((end - start) >>> 1);
			if (array[mid] == value) {
				find = mid;
				break;
			} else if (array[mid] < value) {
				start = mid + 1;
			} else {
				end = mid - 1;
			}
		}
		return find;
	}

	// 二分查找的递归实现
	public static int bsearchInternally(int[] a, int value) {
		return bsearchInternally(a, 0, a.length - 1, value);
	}

	/**
	 * 二分查找的递归实现
	 * 
	 * @param a
	 *            数组
	 * @param value
	 *            要寻找的值
	 * @return 返回的位置，若找不到则为 -1
	 */
	private static int bsearchInternally(int[] a, int low, int high, int value) {
		int find = -1;
		if (low <= high) {
			int mid = low + ((high - low) >>> 1);
			if (a[mid] == value) {
				find = mid;
			} else if (a[mid] < value) {
				find = bsearchInternally(a, mid + 1, high, value);
			} else {
				find = bsearchInternally(a, low, mid - 1, value);
			}
		}
		return find;
	}
	
	/**
	 * 查找第一个值等于给定值的元素
	 */
	public static int searchFirstEquals(int[] a, int value) {
		int low = 0;
		int high = a.length - 1;
		int mid;
		int find = -1;
		while (low <= high) {
			mid = low + ((high - low) >>> 1);
			if (a[mid] == value) {
				if (mid == 0 || a[mid - 1] != value) {
					find = mid;
					break;
				} else {
					high = mid - 1;
				}
			} else if (a[mid] < value) {
				low = mid + 1;
			} else {
				high = mid - 1;
			}
		}
		return find;
	}
	
	/**
	 * 查找最后一个值等于给定值的元素
	 */
	public static int searchLastEquals(int[] a, int value) {
		int low = 0;
		int high = a.length - 1;
		int mid;
		int find = -1;
		while (low <= high) {
			mid = low + ((high - low) >>> 1);
			if (a[mid] == value) {
				if (mid == high || a[mid + 1] != value) {
					find = mid;
					break;
				} else {
					low = mid + 1;
				}
			} else if (a[mid] < value) {
				low = mid + 1;
			} else {
				high = mid - 1;
			}
		}
		return find;
	}
	
	/**
	 * 查找第一个大于等于给定值的元素
	 */
	public static int searchFirstGreateThanEquals(int[] a, int value) {
		int low = 0;
		int high = a.length - 1;
		int mid;
		int find = -1;
		while (low <= high) {
			mid = low + ((high - low) >>> 1);
			if (a[mid] >= value) {
				if (mid == 0 || !(a[mid - 1] >= value)) {
					find = mid;
					break;
				} else {
					high = mid - 1;
				}
			} else {
				low = mid + 1;
			}
		}
		return find;
	}
	
	/**
	 * 查找最后一个小于等于给定值的元素
	 */
	public static int searchLastLessThanEquals(int[] a, int value) {
		int low = 0;
		int high = a.length - 1;
		int mid;
		int find = -1;
		while (low <= high) {
			mid = low + ((high - low) >>> 1);
			if (a[mid] <= value) {
				if (mid == high || !(a[mid + 1] <= value)) {
					find = mid;
					break;
				} else {
					low = mid + 1;
				}
			} else {
				high = mid - 1;
			}
		}
		return find;
	}

}
